package main

import (
	"container/heap"
)

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param input int整型一维数组
 * @param k int整型
 * @return int整型一维数组
 */
func GetLeastNumbers_Solution(input []int, k int) []int {
	// write code here
	//找出第1小的数，第2小的数...第k小的数即可
	h := NodeHeap{}
	heap.Init(&h)

	for i := 0; i < len(input); i++ {
		heap.Push(&h, input[i])
		for h.Len() > k {
			_ = heap.Pop(&h).(int)
		}
	}
	return h
}

// NodeHeap 大根堆
type NodeHeap []int

func (h NodeHeap) Len() int           { return len(h) }
func (h NodeHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h NodeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *NodeHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}
func (h *NodeHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func main() {
	GetLeastNumbers_Solution([]int{4, 5, 1, 6, 2, 7, 3, 8}, 4)
}
